package P1线性结构.LeetCode单调栈;

import P1线性结构.LinkedList;

public class LeetCode84 {
    public int largestRectangleArea(int[] heights) {
        //存储每一个柱子的左边第一小柱子的角标
        int[] left = new int[heights.length];
        //存储每一个柱子的右边第一小柱子的角标
        int[] right = new int[heights.length];
        for (int i = 0; i < heights.length; i++) {
            left[i] = -1;
            right[i] = heights.length;
        }
        LinkedList<Integer> stack = new LinkedList<>();
        //主体逻辑是向右找第一小 构建单调递增栈
        for (int i = 0; i < heights.length; i++) {
            /*
            新来的比栈顶大 那么栈顶就是新来的左边第一小
            新来的比栈顶小 那么新来的就是栈顶右边第一小
            */
            while (!stack.isEmpty() && heights[i] <= heights[stack.peek()]) {
                int top = stack.pop();
                right[top] = i;
            }
            //栈为空 或 新来的比栈顶大 进栈
            left[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }
        int ans = 0;
        for (int i = 0; i < heights.length; i++) {
            ans = Math.max(ans, (right[i] - left[i] - 1) * heights[i]);
        }

        return ans;
    }
}
